Paint house II

Time: O(NxK); Space: O(K); hard

There are a row of n houses, each house can be painted with one of the k colors.

The cost of painting each house with a certain color is different.

You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix.

For example:

  • costs[0][0] is the cost of painting house 0 with color 0;

  • costs[1][2] is the cost of painting house 1 with color 2,

  • and so on…

Find the minimum cost to paint all houses.

Constraints:

  • All costs are positive integers.

Example 1:

Input: costs = [[14,2,11],[11,14,5],[14,3,10]]

Output: 10

Explanation:

  • The three house use color [1,2,1] for each house. The total cost is 10.

Example 2:

Input: costs = [[5]]

Output: 5

Explanation:

  • There is only one color and one house.

Challenge:

  • Could you solve it in O(NxK)?

[8]:

from functools import reduce

class Solution1(object):
    def minCostII(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int
        """
        return min(reduce(self.combine, costs)) if costs else 0

    def combine(self, tmp, house):

        smallest, k, i = min(tmp), len(tmp), tmp.index(min(tmp))

        tmp, tmp[i] = [smallest] * k, min(tmp[:i] + tmp[i+1:])

        return list(map(sum, zip(tmp, house)))

[9]:

s = Solution1()

costs = [[14,2,11],[11,14,5],[14,3,10]]
assert s.minCostII(costs) == 10

costs = [[5]]
assert s.minCostII(costs) == 5

[10]:

class Solution2(object):
    def minCostII(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int
        """
        if not costs:
            return 0

        n = len(costs)
        k = len(costs[0])
        min_cost = [costs[0], [0] * k]

        for i in range(1, n):
            smallest, second_smallest = float("inf"), float("inf")

            for j in range(k):
                if min_cost[(i - 1) % 2][j] < smallest:
                    smallest, second_smallest = min_cost[(i - 1) % 2][j], smallest
                elif min_cost[(i - 1) % 2][j] < second_smallest:
                    second_smallest = min_cost[(i - 1) % 2][j]

            for j in range(k):
                min_j = smallest if min_cost[(i - 1) % 2][j] != smallest else second_smallest
                min_cost[i % 2][j] = costs[i][j] + min_j

        return min(min_cost[(n - 1) % 2])

[11]:

s = Solution2()

costs = [[14,2,11],[11,14,5],[14,3,10]]
assert s.minCostII(costs) == 10

costs = [[5]]
assert s.minCostII(costs) == 5